#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

class Printer{ // 绘图器
  const string fname, m_title;
public:
  Printer(const string &filename, const string &title)
    : fname(filename), m_title(title) {}

  void print(const vector<int> &id, int N) {
    ofstream ofs(fname.c_str());
    ofs << "digraph g{\n";
    ofs << "  rankdir=BT;\n";
    ofs << "  label=\"" << m_title << "\";\n";
    for (int i = 0; i < N; ++i) {
      if (id[i] != i) {
        ofs << "  " << i << " -> " << id[i] << ";\n";
      }
    }
    ofs << "}\n";
  }
};

class IUnionFindSet{ // 并查集接口
public:
  virtual int find(int x) = 0;
  virtual bool union_set(int a, int b) = 0;
  virtual void print(Printer &p) const = 0;
  virtual ~IUnionFindSet() {};
};

class SimpleUnionFindSet : public IUnionFindSet { // 简单实现
  const int N;
  std::vector<int> id;
public:
  SimpleUnionFindSet(int n) : N(n), id(N){
    for(int i = 0; i < N; ++i){
      id[i] = i;
    }
  }

  int find(int x) override {
    while(x != id[x]){
      x = id[x];
    }
    return x;
  }

  virtual bool union_set(int a, int b) override {
    int i = find(a), j = find(b);
    if(i == j){
      return false;
    }
    id[i] = j;
    return true;
  }

  void print(Printer &p) const override {
    p.print(id, N);
  }
};

class RankedUFS : public IUnionFindSet { // 加权合并
  const int N;
  std::vector<int> id, rk;
public:
  RankedUFS(int n) : N(n), id(N), rk(N){
    for(int i = 0; i < N; ++i){
      id[i] = i;
      rk[i] = 1;
    }
  }

  int find(int x) override {
    while(x != id[x]){
      x = id[x];
    }
    return x;
  }

  bool union_set(int a, int b) override {
    int i = find(a), j = find(b);
    if(i == j){
      return false;
    }
    if(rk[i] < rk[j]){ id[i] = j; rk[j] += rk[i]; }
    else             { id[j] = i; rk[i] += rk[j]; }
    return true;
  }

  void print(Printer &p) const override {
    p.print(id, N);
  }
};

class CompressedUFS : public IUnionFindSet { // 路径压缩
  const int N;
  std::vector<int> id;
public:
  CompressedUFS(int n) : N(n), id(N){
    for(int i = 0; i < N; ++i){
      id[i] = i;
    }
  }

  int find(int x) override {
    if(id[x] != x){
      id[x] = find(id[x]);
    }
    return id[x];
  }

  virtual bool union_set(int a, int b) override {
    int i = find(a), j = find(b);
    if(i == j){
      return false;
    }
    id[i] = j;
    return true;
  }

  void print(Printer &p) const override {
    p.print(id, N);
  }
};

class UnionFindSet : public IUnionFindSet { // 完整实现
  const int N;
  std::vector<int> id, rk;
public:
  UnionFindSet(int n) : N(n), id(N), rk(N){
    for(int i = 0; i < N; ++i){
      id[i] = i;
      rk[i] = 1;
    }
  }

  int find(int x) override {
    if(id[x] != x){
      id[x] = find(id[x]);
    }
    return id[x];
  }

  bool union_set(int a, int b) override {
    int i = find(a), j = find(b);
    if(i == j){
      return false;
    }
    if(rk[i] < rk[j]){ id[i] = j; rk[j] += rk[i]; }
    else             { id[j] = i; rk[i] += rk[j]; }
    return true;
  }

  void print(Printer &p) const override {
    p.print(id, N);
  }
};

int main(){
  const int N = 100;
  const int M = N * 1;
  SimpleUnionFindSet s(N);
  RankedUFS r(N);
  CompressedUFS c(N);
  UnionFindSet u(N);
  IUnionFindSet *ufs[] = {&s, &r, &c, &u};
  string suffix[] = {"simple", "ranked", "compressed", "ultimate"};
  string title[] = {"简单实现", "按秩合并", "路径优化", "完整优化"};
  for(int i = 0; i < M; ++i){
    int a = rand() % N, b = rand() % N;
    for(int j = 0; j < 4; ++j){
      ufs[j]->union_set(a, b);
    }
  }
  for (int i = 0; i < 4; ++i) {
    Printer p("ufs-" + suffix[i] + ".dot", "并查集（" + title[i] + "）");
    ufs[i]->print(p);
  }
}
